# -*- coding: utf-8 -*-
# @Time : 2023/9/12 16:30
# @Author  : lining
# @FileName: 图的广度优先遍历-1.py
"""
单纯遍历，没有应用到实际，存储方式为邻接表
edges = [[1,2],[1,3],[2,4],[3,5],[5,6],[4,6],[4,3],[3,2],[5,4]]
"""
class Bfs():
    def __init__(self, start, edges):
        # 边
        self.edges = edges
        # 各顶点是否已经访问过
        self.visited = {}
        # to边
        self.to_edges = {}
        # 访问的队列
        self.visit_list = [start]
        # 访问结果
        self.visite_result = []

    def get_to_edges(self):
        for i in self.edges:
            if i[0] not in self.visited:
                # 放到访问节点里
                self.visited[i[0]] = False
            if i[1] not in self.visited:
                # 放到访问节点里
                self.visited[i[1]] = False
            # 没放在to边就新增这个key
            if i[0] not in self.to_edges:
                self.to_edges[i[0]] = [i[1]]
                continue
            # 已经在to边直接追加
            self.to_edges[i[0]].append(i[1])
        print(self.to_edges)

    def bfs(self):
        while self.visit_list:
            current = self.visit_list[0]
            self.visited[current] = True
            del self.visit_list[0]
            self.visite_result.append(current)
            if current in self.to_edges:
                for i in self.to_edges[current]:
                    if self.visited[i]:
                        continue
                    self.visit_list.append(i)
                    self.visited[i] = True
        print(self.visite_result)

edges = [[1,2],[1,3],[2,4],[3,5],[5,6],[4,6],[4,3],[3,2],[5,4]]
a = Bfs(1, edges)
a.get_to_edges()
a.bfs()
